W2. Множества, алфавиты, формальные языки, операции над языками

Автор

Manuel Mazzara

Дата публикации

29 января 2026 г.

1. Краткое содержание

1.1 Введение в множества

Множество — одно из самых фундаментальных понятий в математике и информатике. Множество — это хорошо определённая совокупность различных объектов, называемых элементами или членами. Говоря «хорошо определённое», мы имеем в виду, что должен быть ясный критерий: принадлежит объект множеству или нет — двусмысленности быть не должно.

Множества можно задать двумя основными способами:

1.1.1 Явное перечисление

Для конечных множеств или когда перечисление уместно, можно описать множество, перечислив все элементы в фигурных скобках. Например: \[A = \{1, 2, 4, 8\}\]

Эта запись говорит, что \(A\) — множество, содержащее ровно числа 1, 2, 4 и 8 и не содержащее других элементов.

Для бесконечных или очень больших конечных множеств иногда используют многоточие, чтобы указать закономерность: \[B = \{0, 3, 6, 9, 12, ...\}\]

Однако такая запись может быть неоднозначной: разные люди могут по-разному понять закономерность.

1.1.2 Задание множества через свойство (нотация с предикатом)

Более надёжный способ — указать свойство, которому должны удовлетворять элементы. Это называется заданием через свойство (set comprehension) или определением множества предикатом:

\[B = \{x \mid x \text{ — неотрицательное целое кратное } 3\}\]

Читается: «\(B\) — множество всех \(x\) таких, что \(x\) — неотрицательное целое кратное 3».

Вертикальная черта «\(\mid\)» означает «таких, что». Такая запись яснее, потому что явно сформулировано правило принадлежности.

1.2 Основные обозначения и отношения между множествами

1.2.1 Принадлежность элемента

Чтобы записать, что элемент принадлежит множеству, используют символ \(\in\) (читается «принадлежит» или «лежит в»): \[2 \in \{1, 2, 3\}\]

Утверждение истинно, потому что 2 действительно является элементом множества \(\{1, 2, 3\}\).

Чтобы записать, что элемент не принадлежит множеству, используют \(\notin\): \[4 \notin \{1, 2, 3\}\]

Это истинно, потому что 4 нет в этом множестве.

1.2.2 Пустое множество

Пустое множество, обозначаемое \(\emptyset\), — особое множество без элементов. Оно единственно: существует ровно одно пустое множество. Пустое множество является подмножеством любого множества (о подмножествах — ниже).

1.2.3 Подмножества

Множество \(A\) — подмножество множества \(B\), пишут \(A \subseteq B\), тогда и только тогда, когда каждый элемент \(A\) также является элементом \(B\). Иными словами, в \(A\) нет ничего, чего не было бы в \(B\).

Пример: \(\{1, 2\} \subseteq \{1, 2, 3, 4\}\), потому что каждый элемент \(\{1, 2\}\) входит и в \(\{1, 2, 3, 4\}\).

Важно: любое множество — подмножество самого себя. Пустое множество \(\emptyset\) — подмножество любого множества.

1.2.4 Равенство множеств

Два множества равны, если и только если у них в точности одни и те же элементы. Математически \(A = B\) тогда и только тогда, когда \(A \subseteq B\) и \(B \subseteq A\). То есть:

каждый элемент \(A\) должен быть в \(B\), и
каждый элемент \(B\) должен быть в \(A\)

1.3 Множества, элементами которых являются множества

Множества могут содержать другие множества как элементы. Например: \[C = \{\{1, 2, 3\}, \{2, 3, 4, 5\}\}\]

Множество \(C\) состоит ровно из двух элементов, и оба — сами множества. Заметьте:

если \(A = \{1, 2, 3\}\), то \(A \in C\) (потому что \(A\) — элемент \(C\))
однако \(1 \notin C\) (число 1 не является прямым элементом \(C\); оно элемент элемента \(C\))

Различие между «\(\in\)» (элемент) и «\(\subseteq\)» (подмножество) здесь принципиально.

1.4 Операции над множествами

Подобно тому, как числа можно складывать и умножать, над множествами можно выполнять операции и получать новые множества. Наиболее распространённые:

1.4.1 Объединение

Объединение двух множеств \(A\) и \(B\), обозначается \(A \cup B\), — это множество всех элементов, принадлежащих \(A\) или \(B\) (или обоим): \[A \cup B = \{x \mid x \in A \lor x \in B\}\]

Здесь «\(\lor\)» — логическое «или».

Пример: если \(A = \{1, 2, 3\}\) и \(B = \{2, 3, 4\}\), то \(A \cup B = \{1, 2, 3, 4\}\). Хотя 2 и 3 встречаются в обоих множествах, в объединении перечисляем их один раз.

1.4.2 Пересечение

Пересечение множеств \(A\) и \(B\), обозначается \(A \cap B\), — множество элементов, принадлежащих и \(A\), и \(B\): \[A \cap B = \{x \mid x \in A \land x \in B\}\]

Здесь «\(\land\)» — логическое «и».

Пример: если \(A = \{1, 2, 3\}\) и \(B = \{2, 3, 4\}\), то \(A \cap B = \{2, 3\}\). Это единственные элементы, лежащие в обоих множествах.

1.4.3 Разность

Разность множеств \(A\) и \(B\), пишут \(A \setminus B\) (иногда \(A - B\)), — множество элементов из \(A\), не лежащих в \(B\): \[A \setminus B = \{x \mid x \in A \land x \notin B\}\]

Пример: если \(A = \{1, 2, 3\}\) и \(B = \{2, 3, 4\}\), то \(A \setminus B = \{1\}\). Остаются только элементы \(A\), которых нет в \(B\).

1.4.4 Объединение многих множеств

Объединение обобщается на любое число множеств. Если есть \(A_0, A_1, A_2, ...\) (возможно, бесконечно много), их объединение обозначают

\[\bigcup_{i=0}^{\infty} A_i\]

или эквивалентно:

\[\bigcup \{A_i \mid i \ge 0\}\]

Это множество всех элементов, принадлежащих хотя бы одному из этих множеств.

1.5 Булеан (множество всех подмножеств)

По любому множеству \(A\) можно построить новое множество из всех подмножеств \(A\). Оно называется булеаном (power set) \(A\), обозначается \(\mathcal{P}(A)\) или иногда \(2^A\).

Пример: булеан \(\{a, b, c\}\): \[\mathcal{P}(\{a, b, c\}) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}\]

В нём \(2^3 = 8\) элементов. Вообще, если в \(A\) ровно \(n\) элементов, то в \(\mathcal{P}(A)\) ровно \(2^n\) элементов.

Почему обозначение \(2^A\)? Идея: у каждого из \(n\) элементов два выбора (включить или исключить), всего \(2^n\) подмножеств.

1.6 Алфавиты и строки

Алфавит — конечное множество символов. Алфавиты обычно обозначают греческой буквой \(\Sigma\). Например:

\(\Sigma = \{0, 1\}\) (двоичный алфавит)
\(\Sigma = \{a, b, c, ..., z\}\) (латиница)
\(\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) (цифры)

Строка (также слово или последовательность) над алфавитом — конечная последовательность символов из этого алфавита. Повторения разрешены.

Примеры над \(\Sigma = \{0, 1\}\):

\(010\) — строка (длина 3)
\(11100011\) — строка (длина 8)
\(1\) — строка (длина 1)

Длина строки \(x\), обозначается \(|x|\), — число символов в строке.

Пустая строка, обозначается \(\epsilon\) (эпсилон) или иногда \(\lambda\), — единственная строка из нуля символов. По определению \(|\epsilon| = 0\).

1.7 Множество всех строк

Для алфавита \(\Sigma\) множество всех строк над \(\Sigma\) (включая пустую) обозначают \(\Sigma^*\). Это бесконечное множество (если только \(\Sigma\) не пусто).

Пример: для \(\Sigma = \{0, 1\}\): \[\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ...\}\]

Обычно строки перечисляют по возрастанию длины: сначала длина 0, затем 1, затем 2 и т.д.

1.8 Конкатенация строк

Как числа складывают, так строки конкатенируют. Если \(x\) и \(y\) — строки, их конкатенация, запись \(xy\) (иногда \(x \cdot y\)), — строка из символов \(x\), за которыми следуют символы \(y\).

Пример:

\(x = "ab"\)
\(y = "bab"\)
\(xy = "abbab"\)

Важные свойства конкатенации:

Ассоциативность: \((xy)z = x(yz)\) для всех строк. От расстановки скобок результат не зависит.
Некоммутативность: вообще говоря, \(xy \neq yx\). Порядок важен!
Нейтральный элемент: \(x\epsilon = \epsilon x = x\). Конкатенация с пустой строкой не меняет строку.

Степенную запись используют для повторной конкатенации: \(a^2 = aa\), \(a^3 = aaa\) и т.д.

1.9 Формальные языки

Язык — множество строк над алфавитом. Точнее, язык \(L\) над \(\Sigma\) — любое подмножество \(\Sigma^*\):

\[L \subseteq \Sigma^*\]

Языки могут быть конечными и бесконечными. Примеры:

над \(\Sigma = \{0, 1\}\): множество всех двоичных строк длины 8 — язык: \(L = \{x \in \{0,1\}^* : |x| = 8\}\)
над \(\Sigma = \{0, 1\}\): множество всех строк, начинающихся с 0: \(L = \{0x : x \in \Sigma^*\}\)
над \(\Sigma = \{a, b, c, ..., z\}\): английские слова образуют язык
над \(\Sigma = \{0, 1, 2, ..., 9\}\): десятичные записи чисел образуют язык

Термин «язык» широк, потому что охватывает и естественные языки (например английский), и формальные конструкции (множества двоичных строк, синтаксис языков программирования).

1.10 Операции над языками

Поскольку язык — множество, к языкам применимы все операции над множествами. Кроме того, из строк можно строить новые языки.

1.10.1 Множественные операции над языками

Основные:

Объединение: \(L_1 \cup L_2 = \{s : s \in L_1 \lor s \in L_2\}\) — строки хотя бы в одном языке
Пересечение: \(L_1 \cap L_2 = \{s : s \in L_1 \land s \in L_2\}\) — строки в обоих языках
Разность: \(L_1 \setminus L_2 = \{s : s \in L_1 \land s \notin L_2\}\) — строки из \(L_1\), не лежащие в \(L_2\)
Дополнение: \(\overline{L} = \Sigma^* \setminus L = \{x \in \Sigma^* : x \notin L\}\) — все строки над \(\Sigma\), не входящие в \(L\)

1.10.2 Конкатенация языков

Если \(L_1\) и \(L_2\) — языки над одним алфавитом \(\Sigma\), их конкатенация:

\[L_1L_2 = \{xy : x \in L_1, y \in L_2\}\]

Это множество всех строк, получаемых взятием строки из \(L_1\) и приписыванием справа строки из \(L_2\).

Пример: если \(L_1 = \{a, aa\}\) и \(L_2 = \{\epsilon, b, ab\}\), то: \[L_1L_2 = \{a, ab, aab, aa, aab, aaab\}\]

Конкатенация языков в общем случае некоммутативна: обычно \(L_1L_2 \neq L_2L_1\).

Есть тонкое замечание: если \(\epsilon \in L_1\), то включение \(L_1 \cdot L_2 \subseteq L_1L_2\) не обязано выполняться в обе стороны.

1.10.3 Степень языка

Степень языка получают повторной конкатенацией языка с самим собой. Для положительного целого \(n\):

\[L^n = \underbrace{L \cdot L \cdot ... \cdot L}_{n \text{ раз}}\]

По определению \(L^0 = \{\epsilon\}\) — язык, состоящий только из пустой строки.

Пример: если \(L = \{a, b\}\), то:

\(L^1 = \{a, b\}\)
\(L^2 = \{aa, ab, ba, bb\}\)
\(L^3 = \{aaa, aab, aba, abb, baa, bab, bba, bbb\}\)

Для алфавита \(\Sigma\) величина \(\Sigma^k\) — все строки точной длины \(k\): \[\Sigma^k = \{x \in \Sigma^* : |x| = k\}\]

1.10.4 Звезда Клини (замыкание Клини)

Звезда Клини — одна из важнейших операций в теории формальных языков. Для языка \(L\) звезда Клини (замыкание Клини) \(L^*\) определяется так:

\[L^* = \{x_1x_2...x_n : n \in \mathbb{N}, x_1, x_2, ..., x_n \in L\} = \bigcup_{n \in \mathbb{N}} L^n\]

Разберём определение:

берём ноль или больше строк из \(L\)
конкатенируем их
\(L^*\) — множество всех таких результатов
часть «ноль или больше» означает, что пустая строка \(\epsilon\) всегда входит в \(L^*\) (ноль строк даёт \(\epsilon\))

Пример: если \(L = \{a\}\), то: \[L^* = \{\epsilon, a, aa, aaa, aaaa, ...\}\]

Это все строки из символа \(a\), повторённого любое число раз (включая ноль раз — получается \(\epsilon\)).

Другой пример: если \(L = \{ab\}\), то: \[L^* = \{\epsilon, ab, abab, ababab, ababab, ...\}\]

Звезду Клини называют «замыканием», потому что результат замкнут относительно конкатенации: если взять две строки из \(L^*\) и склеить, снова получится строка из \(L^*\).

1.10.5 Плюс Клини

Связанная операция — плюс Клини, обозначение \(L^+\), как звезда, но без пустой строки:

\[L^+ = L^* \setminus \{\epsilon\} = \bigcup_{n=1}^{\infty} L^n\]

Это одна или более конкатенаций строк из \(L\) (хотя бы одна обязательна).

Пример: если \(L = \{a\}\), то: \[L^+ = \{a, aa, aaa, aaaa, ...\}\]

Разница: в \(L^*\) есть \(\epsilon\), в \(L^+\) — нет.

1.11 Кратко о специальных обозначениях

Для алфавита \(\Sigma\) и строки \(a\):

\(a^0 = \epsilon\) (по соглашению, любая строка в степени 0 — пустая строка)
\(a^k = \underbrace{aa...a}_{k \text{ раз}}\) (\(k\)-кратная конкатенация \(a\) с собой)
\(\Sigma^k = \{x \in \Sigma^* : |x| = k\}\) (все строки длины ровно \(k\) над \(\Sigma\))
\(\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k\) (все строки любой длины над \(\Sigma\))
\(\Sigma^+ = \Sigma^* \setminus \{\epsilon\}\) (все непустые строки над \(\Sigma\))

2. Определения

Алфавит: конечное множество символов, обычно обозначается \(\Sigma\). Примеры: \(\{0, 1\}\), \(\{a, b, c, ..., z\}\) или любое конечное множество различных символов.
Строка (также слово или последовательность): конечная последовательность символов алфавита, повторения разрешены. Длина строки \(x\), \(|x|\), — число содержащихся в ней символов.
Пустая строка: единственная строка без символов, обозначается \(\epsilon\) (эпсилон). По определению \(|\epsilon| = 0\).
Множество: хорошо определённая совокупность различных объектов — элементов. Множество определяется тем, какие объекты в него входят: для любого объекта либо он элемент, либо нет (без двусмысленности).
Элемент: объект, принадлежащий множеству. Пишем \(x \in A\), если \(x\) — элемент \(A\), и \(x \notin A\), если нет.
Подмножество: \(A\) — подмножество \(B\), пишут \(A \subseteq B\), если каждый элемент \(A\) также элемент \(B\). Любое множество — подмножество самого себя; пустое множество — подмножество любого множества.
Пустое множество: единственное множество без элементов, \(\emptyset\). Подмножество любого множества.
Равенство множеств: \(A\) и \(B\) равны (\(A = B\)) тогда и только тогда, когда у них одни и те же элементы, т.е. \(A \subseteq B\) и \(B \subseteq A\).
Объединение множеств: \(A \cup B\) — множество элементов, принадлежащих \(A\) или \(B\) (или обоим): \(A \cup B = \{x \mid x \in A \lor x \in B\}\).
Пересечение множеств: \(A \cap B\) — элементы, принадлежащие и \(A\), и \(B\): \(A \cap B = \{x \mid x \in A \land x \in B\}\).
Разность множеств: \(A \setminus B\) или \(A - B\) — элементы из \(A\), не лежащие в \(B\): \(A \setminus B = \{x \mid x \in A \land x \notin B\}\).
Булеан (power set): \(\mathcal{P}(A)\) или \(2^A\) — множество всех подмножеств \(A\), включая \(\emptyset\) и само \(A\). Если \(|A| = n\), то \(|\mathcal{P}(A)| = 2^n\).
Задание через свойство (set comprehension): способ задать множество свойством элементов: \(A = \{x \mid P(x)\}\) означает «\(A\) — множество всех \(x\), для которых истинно \(P(x)\)».
Язык: язык \(L\) над \(\Sigma\) — множество строк над \(\Sigma\), т.е. любое подмножество \(\Sigma^*\). Языки бывают конечными и бесконечными.
\(\Sigma^*\): множество всех строк над \(\Sigma\), включая пустую; \(\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k\).
Конкатенация строк: склейка двух строк конец-в-начало. Для строк \(x\) и \(y\) конкатенация \(xy\) (или \(x \cdot y\)) — символы \(x\), затем символы \(y\). Ассоциативна, в общем случае не коммутативна.
Конкатенация языков: \(L_1L_2 = \{xy : x \in L_1, y \in L_2\}\) — все строки из строки из \(L_1\) и строки из \(L_2\).
Степень языка: \(L^n\) — \(n\)-кратная конкатенация \(L\) с собой. По соглашению \(L^0 = \{\epsilon\}\).
Звезда Клини (замыкание Клини): \(L^*\) — все строки, получаемые конкатенацией нуля или более строк из \(L\): \(L^* = \bigcup_{n=0}^{\infty} L^n\). Всегда содержит \(\epsilon\).
Плюс Клини: \(L^+ = L^* \setminus \{\epsilon\} = \bigcup_{n=1}^{\infty} L^n\) — без пустой строки.
Дополнение языка: для \(L\) над \(\Sigma\) дополнение \(\overline{L}\) (или \(L^c\)) — все строки над \(\Sigma\), не входящие в \(L\): \(\overline{L} = \Sigma^* \setminus L = \{x \in \Sigma^* \mid x \notin L\}\).
Мощность (cardinality): для конечного \(A\) число \(|A|\) — число элементов. Для бесконечных множеств мощность — более абстрактное понятие «размера».
Свободный моноид (free monoid): \(\Sigma^*\) с операцией конкатенации строк (string concatenation). Моноид — множество с ассоциативной бинарной операцией и нейтральным элементом (здесь \(\epsilon\)). «Свободный» значит отсутствие дополнительных ограничений на склейку строк.

3. Формулы

Объединение: \(A \cup B = \{x \mid x \in A \lor x \in B\}\)
Пересечение: \(A \cap B = \{x \mid x \in A \land x \in B\}\)
Разность: \(A \setminus B = \{x \mid x \in A \land x \notin B\}\)
Объединение семейства множеств: \(\bigcup_{i=0}^{\infty} A_i = \{x \mid x \in A_i \text{ для некоторого } i \geq 0\}\)
Мощность булеана: если \(|A| = n\), то \(|\mathcal{P}(A)| = 2^n\)
Длина строки: \(|x|\) — число символов в \(x\); \(|\epsilon| = 0\)
Конкатенация строк: \(xy\) — символы \(x\), затем символы \(y\)
Ассоциативность конкатенации: \((xy)z = x(yz)\) для всех строк
Нейтральный элемент конкатенации: \(x\epsilon = \epsilon x = x\) для любой строки \(x\)
Степень строки: \(a^k = \underbrace{aa...a}_{k \text{ раз}}\) при \(k > 0\); \(a^0 = \epsilon\)
Конкатенация языков: \(L_1L_2 = \{xy : x \in L_1, y \in L_2\}\)
Степень языка: \(L^n = \{x_1x_2...x_n : x_i \in L \text{ для всех } 1 \leq i \leq n\}\); \(L^0 = \{\epsilon\}\)
Звезда Клини: \(L^* = \bigcup_{n=0}^{\infty} L^n = \{x_1x_2...x_n \mid n \in \mathbb{N}, x_i \in L\}\)
Плюс Клини: \(L^+ = L^* \setminus \{\epsilon\} = \bigcup_{n=1}^{\infty} L^n\)
Строки фиксированной длины: \(\Sigma^k = \{x \in \Sigma^* \mid |x| = k\}\)
Все строки над алфавитом: \(\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k\)
Все непустые строки: \(\Sigma^+ = \Sigma^* \setminus \{\epsilon\}\)
Дополнение языка: \(\overline{L} = \Sigma^* \setminus L = \{x \in \Sigma^* \mid x \notin L\}\)

4. Примеры

4.1. Определение множества по описанию (Лаба 2, Задание 1.1)

Определите множество \(D = \{\{x\} \mid x \text{ — неотрицательное целое и } x \le 4\}\).

Показать решение

Ключевая идея: это множество состоит из одноэлементных множеств. Нужно перечислить такие \(\{x\}\), где \(x\) — неотрицательное целое не больше 4.

Найти неотрицательные целые по условию: нужно \(x \leq 4\) и \(x \geq 0\), значит \(x \in \{0, 1, 2, 3, 4\}\).
Построить одноэлементные множества:
- при \(x = 0\): \(\{0\}\)
- при \(x = 1\): \(\{1\}\)
- при \(x = 2\): \(\{2\}\)
- при \(x = 3\): \(\{3\}\)
- при \(x = 4\): \(\{4\}\)
Собрать их в \(D\): \[D = \{\{0\}, \{1\}, \{2\}, \{3\}, \{4\}\}\]

Ответ: \(D = \{\{0\}, \{1\}, \{2\}, \{3\}, \{4\}\}\)

4.2. Определение множества по описанию (Лаба 2, Задание 1.2)

Определите множество \(E = \{3i + 5j \mid i \text{ и } j \text{ — неотрицательные целые}\}\).

Показать решение

Ключевая идея: это множество всех неотрицательных целых линейных комбинаций 3 и 5. Нужно понять, какие неотрицательные целые представимы в виде \(3i + 5j\).

Перечислить элементы: подберём значения \(i\) и \(j\):
- \(i=0, j=0\): \(3(0) + 5(0) = 0\)
- \(i=1, j=0\): \(3(1) + 5(0) = 3\)
- \(i=0, j=1\): \(3(0) + 5(1) = 5\)
- \(i=2, j=0\): \(3(2) + 5(0) = 6\)
- \(i=1, j=1\): \(3(1) + 5(1) = 8\)
- \(i=3, j=0\): \(3(3) + 5(0) = 9\)
- \(i=0, j=2\): \(3(0) + 5(2) = 10\)
- и так далее…
Какие числа представимы: можно показать, что любое неотрицательное целое, кроме 1, 2, 4 и 7, представимо в виде \(3i + 5j\). Это связано с задачей Фробениуса для монет 3 и 5: наибольшая невыразимая сумма равна \(3 \cdot 5 - 3 - 5 = 7\).
Явная запись множества: \[E = \{0, 3, 5, 6, 8, 9, 10, 11, 12, ...\} = \{n \in \mathbb{Z}^+ \cup \{0\} \mid n \neq 1, 2, 4, 7\}\]

Ответ: \(E = \{0, 3, 5, 6, 8, 9, 10, 11, 12, ...\}\) (все неотрицательные целые, кроме 1, 2, 4 и 7)

4.3. Равенство множеств (Лаба 2, Задание 1.3)

Равны ли множества \(\{0, 1\}\) и \(\{1, 0\}\)?

Показать решение

Ключевая идея: множество определяется только составом элементов, а не порядком перечисления.

Элементы первого множества: в \(\{0, 1\}\) — 0 и 1.
Элементы второго множества: в \(\{1, 0\}\) — 1 и 0.
Сравнение: в обоих ровно элементы 0 и 1.
Равенство: два множества равны тогда и только тогда, когда совпадают элементы. Значит \(\{0, 1\} = \{1, 0\}\).

Ответ: да, \(\{0, 1\} = \{1, 0\}\). Порядок в записи множества не важен.

4.4. Равенство и повторы (Лаба 2, Задание 1.4)

Равны ли множества \(\{0, 1, 2, 1, 0\}\) и \(\{1, 1, 1, 1, 0, 2, 2\}\)?

Показать решение

Ключевая идея: в фигурных скобках повторы не создают «дополнительных» элементов; важны только различные элементы.

Различные элементы первого множества: в \(\{0, 1, 2, 1, 0\}\) встречаются 0, 1 и 2 — множество различных: \(\{0, 1, 2\}\).
Различные элементы второго множества: в \(\{1, 1, 1, 1, 0, 2, 2\}\) — снова \(\{0, 1, 2\}\).
Сравнение: совпадают.
Вывод: обе записи задают одно и то же множество.

Ответ: да, \(\{0, 1, 2, 1, 0\} = \{1, 1, 1, 1, 0, 2, 2\} = \{0, 1, 2\}\).

4.5. Построение булеана (Лаба 2, Задание 2.1)

Постройте булеан множества \(\{a, b\}\).

Показать решение

Ключевая идея: булеан содержит все подмножества, включая \(\emptyset\) и само множество.

Все подмножества \(\{a, b\}\):
- без элементов: \(\emptyset\)
- по одному элементу: \(\{a\}\), \(\{b\}\)
- оба элемента: \(\{a, b\}\)
Полнота: для каждого элемента выбор «включить / не включить»:
- исключить \(a\) и \(b\): \(\emptyset\)
- только \(a\): \(\{a\}\)
- только \(b\): \(\{b\}\)
- оба: \(\{a, b\}\)
Счёт: 2 элемента \(\Rightarrow\) \(2^2 = 4\) подмножества — перечислены все.

Ответ: \(\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}\)

4.6. Построение булеана (Лаба 2, Задание 2.2)

Постройте булеан \(\{0, 1\} \cup \{1, 2\}\).

Показать решение

Ключевая идея: сначала упростить множество (объединение), затем перечислить подмножества.

Объединение: \(\{0, 1\} \cup \{1, 2\} = \{0, 1, 2\}\).
Подмножества \(\{0, 1, 2\}\):
- 0 элементов: \(\emptyset\)
- 1 элемент: \(\{0\}\), \(\{1\}\), \(\{2\}\)
- 2 элемента: \(\{0, 1\}\), \(\{0, 2\}\), \(\{1, 2\}\)
- 3 элемента: \(\{0, 1, 2\}\)
Счёт: 3 элемента \(\Rightarrow\) \(2^3 = 8\) подмножеств.

Ответ: \(\mathcal{P}(\{0, 1, 2\}) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\}\)

4.7. Построение булеана (Лаба 2, Задание 2.3)

Постройте булеан \(\{z\}\).

Показать решение

Ключевая идея: у одноэлементного множества ровно \(2^1 = 2\) подмножества.

Подмножества \(\{z\}\):
- \(\emptyset\)
- \(\{z\}\)

Ответ: \(\mathcal{P}(\{z\}) = \{\emptyset, \{z\}\}\)

4.8. Операции и булеан (Лаба 2, Задание 2.4)

Постройте булеан \(\{0, 1, 2, 3, 4\} \cap \{1, 3, 5, a\}\).

Показать решение

Ключевая идея: сначала пересечение, затем булеан.

Пересечение: элементы, лежащие в обоих множествах.
- 0 только в первом — нет.
- 1 в обоих — да.
- 2 только в первом — нет.
- 3 в обоих — да.
- 4 только в первом — нет.
- 5 только во втором — нет.
- \(a\) только во втором — нет.
Итого: \(\{0, 1, 2, 3, 4\} \cap \{1, 3, 5, a\} = \{1, 3\}\)
Булеан \(\{1, 3\}\):
- \(\emptyset\)
- \(\{1\}\)
- \(\{3\}\)
- \(\{1, 3\}\)

Ответ: \(\mathcal{P}(\{1, 3\}) = \{\emptyset, \{1\}, \{3\}, \{1, 3\}\}\)

4.9. Операции и булеан (Лаба 2, Задание 2.5)

Постройте булеан \(\{0, 1, 2, 3\} \setminus \{1, 3, 5, a\}\).

Показать решение

Ключевая идея: сначала разность, затем булеан.

Разность: элементы первого, которых нет во втором.
- 0: в первом, не во втором — да.
- 1: в обоих — нет.
- 2: в первом, не во втором — да.
- 3: в обоих — нет.
Итого: \(\{0, 1, 2, 3\} \setminus \{1, 3, 5, a\} = \{0, 2\}\)
Булеан \(\{0, 2\}\):
- \(\emptyset\)
- \(\{0\}\)
- \(\{2\}\)
- \(\{0, 2\}\)

Ответ: \(\mathcal{P}(\{0, 2\}) = \{\emptyset, \{0\}, \{2\}, \{0, 2\}\}\)

4.10. Булеан пустого множества (Лаба 2, Задание 2.6)

Постройте булеан \(\emptyset\).

Показать решение

Ключевая идея: единственное подмножество пустого множества — само пустое множество.

Подмножества \(\emptyset\): только \(\emptyset\).
Счёт: 0 элементов \(\Rightarrow\) \(2^0 = 1\) подмножество.

Ответ: \(\mathcal{P}(\emptyset) = \{\emptyset\}\)

4.11. Основы формального языка (Лаба 2, Задание 2.7)

Определите \(\Sigma^0\) для любого алфавита \(\Sigma\).

Показать решение

Ключевая идея: \(\Sigma^k\) — все строки длины ровно \(k\). Значит \(\Sigma^0\) — строки длины 0.

Строки длины 0: существует ровно одна — \(\epsilon\).
Вывод: \(\Sigma^0 = \{\epsilon\}\)

Ответ: \(\Sigma^0 = \{\epsilon\}\) для любого алфавита \(\Sigma\).

4.12. Все строки заданной длины (Лаба 2, Задание 2.8)

Определите \(\Sigma^4\) для \(\Sigma = \{0, 1\}\).

Показать решение

Ключевая идея: \(\Sigma^4\) — все двоичные строки длины 4.

Число строк: на каждой из 4 позиций 0 или 1, всего \(2^4 = 16\) строк.
Перечисление:
- с префиксом 00: \(0000, 0001, 0010, 0011\)
- с префиксом 01: \(0100, 0101, 0110, 0111\)
- с префиксом 10: \(1000, 1001, 1010, 1011\)
- с префиксом 11: \(1100, 1101, 1110, 1111\)

Ответ: \(\Sigma^4 = \{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111\}\)

4.13. Булеан алфавита (Лаба 2, Задание 2.9)

Определите \(\mathcal{P}(\Sigma)\) для \(\Sigma = \{0, 1\}\).

Показать решение

Ключевая идея: \(\mathcal{P}(\Sigma)\) — множество всех подмножеств самого алфавита.

Подмножества \(\{0, 1\}\):
- \(\emptyset\)
- \(\{0\}\), \(\{1\}\)
- \(\{0, 1\}\)
Счёт: 2 элемента \(\Rightarrow\) 4 подмножества.

Ответ: \(\mathcal{P}(\Sigma) = \{\emptyset, \{0\}, \{1\}, \{0, 1\}\}\)

4.14. Булеан множества всех строк (Лаба 2, Задание 2.10)

Определите \(\mathcal{P}(\Sigma^*)\) для \(\Sigma = \{0, 1\}\).

Показать решение

Ключевая идея: \(\Sigma^*\) бесконечно; \(\mathcal{P}(\Sigma^*)\) — множество всех его подмножеств.

Структура: \(\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, ...\}\) — все конечные двоичные строки.
\(\mathcal{P}(\Sigma^*)\): булеан бесконечного множества бесконечен (более того, мощность выше, чем у \(\Sigma^*\)).
Примеры элементов \(\mathcal{P}(\Sigma^*)\):
- \(\emptyset\) (пустой язык)
- \(\{\epsilon\}\)
- \(\{0, 1\}\)
- \(\Sigma^*\)
- множество всех строк, начинающихся с 0
- множество всех строк чётной длины
- любое другое подмножество \(\Sigma^*\)

Ответ: \(\mathcal{P}(\Sigma^*)\) — множество всех подмножеств \(\Sigma^*\) (все возможные языки над \(\Sigma\)). Это несчётно бесконечное множество; говорят также о «\(2^{\infty}\)» элементах в интуитивном смысле.

4.15. Алфавиты для языков (Лаба 2, Задание 3.1)

Укажите возможный алфавит для языка \(L = \{oh, ouch, ugh\}\).

Показать решение

Ключевая идея: алфавит должен содержать все символы, встречающиеся в строках языка.

Строки: \(L = \{oh, ouch, ugh\}\)
Символы:
- в «oh»: \(o\), \(h\)
- в «ouch»: \(o\), \(u\), \(c\), \(h\)
- в «ugh»: \(u\), \(g\), \(h\)
Совокупность: \(\{o, u, h, c, g\}\)
Проверка: каждая строка составлена только из этих символов.

Ответ: например \(\Sigma = \{o, u, h, c, g\}\) (или любое надмножество).

4.16. Алфавиты для языков (Лаба 2, Задание 3.2)

Укажите возможный алфавит для языка \(L = \{apple, pear, 4711\}\).

Показать решение

Ключевая идея: в алфавит входят все символы, встречающиеся в строках языка.

Символы:
- в «apple»: \(a, p, l, e\)
- в «pear»: \(p, e, a, r\)
- в «4711»: \(4, 7, 1\)
Без повторов: \(\{a, p, l, e, r, 4, 7, 1\}\)

Ответ: например \(\Sigma = \{a, p, l, e, r, 4, 7, 1\}\) (или любое надмножество).

4.17. Алфавиты для языков (Лаба 2, Задание 3.3)

Укажите возможный алфавит для языка всех двоичных строк.

Показать решение

Ключевая идея: двоичные строки используют только 0 и 1.

Нужные символы: последовательности из нулей и единиц.

Ответ: \(\Sigma = \{0, 1\}\)

4.18. Звезда Клини на разных алфавитах (Лаба 2, Задание 3.4)

Что даёт \(\Sigma^*\) при \(\Sigma = \{0, 1\}\)?

Показать решение

Ключевая идея: \(\Sigma^*\) — все строки (любой длины) над \(\Sigma\).

Описание: \(\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ...\}\)
Смысл: все конечные двоичные строки, включая пустую.

Ответ: \(\{0, 1\}^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...\}\) (все двоичные строки любой длины)

4.19. Звезда Клини на разных алфавитах (Лаба 2, Задание 3.5)

Что даёт \(\Sigma^*\) при \(\Sigma = \{a\}\)?

Показать решение

Ключевая идея: при одном символе в алфавите \(\Sigma^*\) — все повторы этого символа.

По длинам:
- длина 0: \(\epsilon\)
- длина 1: \(a\)
- длина 2: \(aa\)
- длина 3: \(aaa\)
- и т.д.
Запись: \(\Sigma^* = \{\epsilon, a, aa, aaa, aaaa, ...\} = \{a^n \mid n \in \mathbb{N}\}\)

Ответ: \(\{a\}^* = \{\epsilon, a, aa, aaa, aaaa, ...\} = \{a^n \mid n \geq 0\}\)

4.20. Звезда Клини от пустого алфавита (Лаба 2, Задание 3.6)

Что даёт \(\Sigma^*\) при \(\Sigma = \emptyset\) (пустой алфавит)?

Показать решение

Ключевая идея: без символов нельзя построить непустую строку; остаётся только пустая.

Анализ: непустая строка требует хотя бы один символ из алфавита — их нет.

Ответ: \(\emptyset^* = \{\epsilon\}\) (только пустая строка)

4.21. Определение алфавита (Лаба 2, Задание 4.1)

Для языка \(L = \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, ...\}\) определите алфавит \(\Sigma\).

Показать решение

Ключевая идея: смотрим, какие символы встречаются в строках языка.

Наблюдение: язык содержит все строки из символов 0 и 1.
Алфавит: только 0 и 1.

Ответ: \(\Sigma = \{0, 1\}\)

4.22. Определение алфавита (Лаба 2, Задание 4.2)

Для языка \(L = \Sigma^* = \{\epsilon, a, aa, aaa, aaaa, ...\}\) определите алфавит \(\Sigma\).

Показать решение

Ключевая идея: какие символы появляются в языке.

Наблюдение: все строки — повторы символа \(a\).

Ответ: \(\Sigma = \{a\}\)

4.23. Дополнение языка (Лаба 2, Задание 4.3)

Пусть \(\Sigma = \{0, 1\}\). Постройте дополнение \(\overline{L}\) для \(L = \{010, 101, 11\}\).

Показать решение

Ключевая идея: дополнение — все строки над \(\Sigma\), не входящие в \(L\).

Определение: \(\overline{L} = \Sigma^* \setminus L = \{x \in \{0,1\}^* : x \notin L\}\)
Описание: все двоичные строки, кроме 010, 101 и 11. В частности:
- \(\epsilon\)
- строки длины 1: \(0, 1\)
- строки длины 2: \(00, 01, 10\) (11 исключена)
- строки длины 3, кроме 010 и 101: \(000, 001, 011, 100, 110, 111\)
- все строки длины 4 и далее
Явно: \[\overline{L} = \{\epsilon, 0, 1, 00, 01, 10, 000, 001, 011, 100, 110, 111, 0000, ...\} \setminus \{010, 101, 11\}\]

Ответ: \(\overline{L} = \{x \in \{0,1\}^* : x \notin \{010, 101, 11\}\}\) (все двоичные строки, кроме 010, 101 и 11)

4.24. Дополнение языка (Лаба 2, Задание 4.4)

Пусть \(\Sigma = \{0, 1\}\). Постройте дополнение \(\overline{L}\) для \(L = \Sigma^* \setminus \{110\}\).

Показать решение

Ключевая идея: нужно дополнение к языку «все строки, кроме 110».

Исходный язык: \(L = \Sigma^* \setminus \{110\}\) — все двоичные строки, кроме 110.
Дополнение: \[\overline{L} = \Sigma^* \setminus L = \Sigma^* \setminus (\Sigma^* \setminus \{110\})\]

По теории множеств \(\Sigma^* \setminus (\Sigma^* \setminus \{110\}) = \{110\}\)
Проверка: \(\Sigma^*\) разбивается на строки из \(L\) и единственную строку 110.

Ответ: \(\overline{L} = \{110\}\)

4.25. Разность булеанов (Лаба 2, Задание 4.5)

Определите множество \(\mathcal{P}(\{a, b\}) \setminus \mathcal{P}(\{a, c\})\).

Показать решение

Ключевая идея: сначала булеаны, затем разность.

\(\mathcal{P}(\{a, b\})\): \[\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}\]
\(\mathcal{P}(\{a, c\})\): \[\mathcal{P}(\{a, c\}) = \{\emptyset, \{a\}, \{c\}, \{a, c\}\}\]
Разность: элементы первого, отсутствующие во втором.
- \(\emptyset\) и \(\{a\}\) — в обоих
- \(\{b\}\) — только в первом
- \(\{a, b\}\) — только в первом
Результат: \[\mathcal{P}(\{a, b\}) \setminus \mathcal{P}(\{a, c\}) = \{\{b\}, \{a, b\}\}\]

Ответ: \(\{\{b\}, \{a, b\}\}\)

4.26. Задание через свойство (Лаба 2, Задание 4.6)

Определите множество \(\{x \mid x, y \in \mathbb{N} \land \exists y : y < 10 \land (y + 2 = x)\}\), где \(\mathbb{N}\) — множество всех неотрицательных целых.

Показать решение

Ключевая идея: это значения \(x\), для которых существует \(y < 10\) с \(x = y + 2\).

Условие: \(x \in \mathbb{N}\) и \(\exists y \in \mathbb{N}: y < 10,\; y + 2 = x\).
Перебор: \(y \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\).
- \(y = 0 \Rightarrow x = 2\)
- \(y = 1 \Rightarrow x = 3\)
- …
- \(y = 9 \Rightarrow x = 11\)
Итог: \(x \in \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\)

Ответ: \(\{2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\)

4.27. Конкатенация языков (Лаба 2, Задание 5.1)

Пусть \(L = \{a^i : i \geq 0\} = \{\epsilon, a, aa, aaa, ...\}\) — язык над \(\Sigma = \{a, b\}\). Найдите \(\bar{L}\) и \(L^*\).

Показать решение

Ключевая идея: \(L\) — пустая строка и строки из подряд идущих \(a\) без \(b\). Нужны дополнение и звезда Клини.

(a) Дополнение \(\bar{L}\):

\(L\): \(\{\epsilon, a, aa, aaa, aaaa, ...\}\) — только \(a\), без \(b\).
\(\bar{L} = \Sigma^* \setminus L\) — все строки над \(\{a, b\}\), не из \(L\).
Характеризация: строки, в которых есть хотя бы один \(b\).
Запись: \(\bar{L} = \{x \in \{a, b\}^* : x \text{ содержит хотя бы один } b\}\)

(b) Звезда Клини \(L^*\):

Определение: \(L^* = \{x_1x_2...x_n : n \in \mathbb{N}, x_i \in L\}\)
Анализ: конкатенируем ноль или более строк вида \(a^i\), \(i \geq 0\).
Склейка: \(a^{i_1} \cdot a^{i_2} \cdot ... \cdot a^{i_k} = a^{i_1 + i_2 + ... + i_k}\)
Вывод: сумма неотрицательных целых даёт любое неотрицательное целое в показателе: \[L^* = \{\epsilon, a, aa, aaa, aaaa, ...\} = L\]

Ответ:

\(\bar{L} = \{x \in \{a, b\}^* : x \text{ содержит хотя бы один } b\}\)
\(L^* = \{a^i : i \geq 0\} = L\)

4.28. Конкатенация языков (пример) (Лаба 2, Задание 5.2)

Пусть \(L_1 = \{\epsilon, a, aa\}\) и \(L_2 = \{aa, aaa\}\) над \(\Sigma = \{a, b\}\). Найдите \(L_1L_2\).

Показать решение

Ключевая идея: \(L_1L_2\) — все склейки \(xy\), \(x \in L_1\), \(y \in L_2\).

Элементы: \(L_1\) — 3 строки, \(L_2\) — 2 строки.
Все склейки:
- \(\epsilon \cdot aa = aa\)
- \(\epsilon \cdot aaa = aaa\)
- \(a \cdot aa = aaa\)
- \(a \cdot aaa = aaaa\)
- \(aa \cdot aa = aaaa\)
- \(aa \cdot aaa = aaaaa\)
Без дубликатов: \(L_1L_2 = \{aa, aaa, aaaa, aaaaa\}\)

Ответ: \(L_1L_2 = \{aa, aaa, aaaa, aaaaa\}\)

4.29. Конкатенация языков (пример) (Лаба 2, Задание 5.3)

Пусть \(L_1 = \{a, a^2, a^4\}\) и \(L_2 = \{b^0, b^2, b^3\}\) над \(\Sigma = \{a, b\}\). Найдите \(L_1L_2\).

Показать решение

Ключевая идея: раскрыть степени; \(b^0 = \epsilon\).

Явно:
- \(L_1 = \{a, aa, aaaa\}\)
- \(L_2 = \{\epsilon, bb, bbb\}\)
Все произведения:
- \(a \cdot \epsilon = a\), \(a \cdot bb = abb\), \(a \cdot bbb = abbb\)
- \(aa \cdot \epsilon = aa\), \(aa \cdot bb = aabb\), \(aa \cdot bbb = aabbb\)
- \(aaaa \cdot \epsilon = aaaa\), \(aaaa \cdot bb = aaaabb\), \(aaaa \cdot bbb = aaaabbb\)
Результат: \[L_1L_2 = \{a, abb, abbb, aa, aabb, aabbb, aaaa, aaaabb, aaaabbb\}\]

Ответ: \(\{a, abb, abbb, aa, aabb, aabbb, aaaa, aaaabb, aaaabbb\}\)

4.30. Степень языка (Лаба 2, Задание 5.4)

Пусть \(L = \{0, 01, 001\}\). Найдите \(L^2\).

Показать решение

Ключевая идея: \(L^2 = L \cdot L\) — все склейки двух строк из \(L\).

\(L = \{0, 01, 001\}\)
Пары:
- \(0 \cdot 0 = 00\), \(0 \cdot 01 = 001\), \(0 \cdot 001 = 0001\)
- \(01 \cdot 0 = 010\), \(01 \cdot 01 = 0101\), \(01 \cdot 001 = 01001\)
- \(001 \cdot 0 = 0010\), \(001 \cdot 01 = 00101\), \(001 \cdot 001 = 001001\)
Дубликатов нет.

Ответ: \(L^2 = \{00, 001, 0001, 010, 0101, 01001, 0010, 00101, 001001\}\)

4.31. Описание языка словами (Лаба 2, Задание 5.5)

Опишите словами язык \(L = \{a, b\}^*\) над \(\Sigma = \{a, b\}\).

Показать решение

Ключевая идея: \(\{a, b\}^*\) — звезда Клини двухсимвольного множества: все конечные склейки \(a\) и \(b\).

Нотация: \(\{a, b\}^*\) — все строки из символов \(a\) и \(b\).
Состав:
- \(\epsilon\)
- длина 1: \(a, b\)
- длина 2: \(aa, ab, ba, bb\)
- длина 3: \(aaa, aab, aba, abb, baa, bab, bba, bbb\)
- и далее…

Ответ: язык всех конечных строк над алфавитом \(\{a, b\}\), включая пустую строку. Эквивалентно: все последовательности из \(a\) и \(b\) любой (конечной) длины.

4.32. Описание языка словами (Лаба 2, Задание 5.6)

Опишите словами язык \(L = \{a\}^* \cup \{b\}^*\) над \(\Sigma = \{a, b\}\).

Показать решение

Ключевая идея: объединение двух звёзд Клини — строки только из \(a\) или только из \(b\).

\(\{a\}^*\): \(\{\epsilon, a, aa, aaa, ...\}\)
\(\{b\}^*\): \(\{\epsilon, b, bb, bbb, ...\}\)
Объединение: \(\{a\}^* \cup \{b\}^* = \{\epsilon, a, aa, aaa, ..., b, bb, bbb, ...\}\)

Ответ: язык всех строк, состоящих либо только из \(a\), либо только из \(b\) (пустая строка входит в оба слагаемых). Иными словами: строка не содержит одновременно символы \(a\) и \(b\).

4.33. Описание языка словами (Лаба 2, Задание 5.7)

Опишите словами язык \(L = \{a\}^* \cap \{b\}^*\) над \(\Sigma = \{a, b\}\).

Показать решение

Ключевая идея: в пересечении — то, что есть и там, и там.

\(\{a\}^*\): строки без \(b\)
\(\{b\}^*\): строки без \(a\)
Пересечение: одновременно без \(b\) и без \(a\) — только \(\epsilon\).
Итог: \(L = \{\epsilon\}\)

Ответ: язык, состоящий только из пустой строки: \(\{\epsilon\}\)

4.34. Описание языка словами (Лаба 2, Задание 5.8)

Опишите словами язык \(L = \{aa\}^* \setminus \{aaaa\}^*\) над \(\Sigma = \{a, b\}\).

Показать решение

Ключевая идея: разность языков, связанных с чётными повторами \(a\).

\(\{aa\}^*\): конкатенации строки «aa»: \[\{aa\}^* = \{\epsilon, aa, aaaa, aaaaaa, aaaaaaaa, ...\} = \{a^{2n} : n \geq 0\}\] — все строки из \(a\) чётной длины.
\(\{aaaa\}^*\): \[\{aaaa\}^* = \{\epsilon, aaaa, aaaaaaaa, aaaaaaaaaaaa, ...\} = \{a^{4n} : n \geq 0\}\] — длина делится на 4.
Разность: в первом, но не во втором — чётная длина, не кратная 4.
Характеризация: длины \(2, 6, 10, 14, 18, ...\), т.е. длина \(\equiv 2 \pmod{4}\)

Ответ: строки из символов \(a\) чётной длины, но с длиной не кратной 4. Примеры: \(aa, aaaaaa, aaaaaaaaaa, ...\)

4.35. Раскрытие степенной записи (Лаба 2, Задание 5.9)

Запишите явно: \(0^5, 0^31^3, (010)^2, (01)^30, 1^0\).

Показать решение

Ключевая идея: степень — повторение строки или символа.

\(0^5\): пять нулей: \(00000\)
\(0^31^3\): три нуля и три единицы: \(000111\)
\((010)^2\): «010» два раза: \(010010\)
\((01)^30\): в формулировке задания опечатка; по смыслу имеется в виду \((01)^3\) и затем символ \(0\): \(0101010\)
\(1^0\): степень 0 даёт пустую строку: \(\epsilon\)

Ответ:

\(0^5 = 00000\)
\(0^31^3 = 000111\)
\((010)^2 = 010010\)
\((01)^30 = 0101010\)
\(1^0 = \epsilon\) (пустая строка)

4.36. Сложные операции над языками (Лаба 2, Задание 6.1)

Рассмотрим языки над \(\Sigma = \{0, 1\}\):

\(L_1 = \{0, 1, 00, 11, 000, 111, ...\}\) \(L_2 = \{0, 1\}^*\) \(L_3 = \{w \mid w \in \Sigma^*, |w| = 1\}\) \(L_4 = \{w \mid w \in \Sigma^*, |w| = 2\}\) \(L_5 = \{w \mid w \in \Sigma^*, |w| \geq 1\}\)

Найти: 1. \(L_1 \cup L_2\) и \(L_3 \cup L_4\) 2. \(L_1 \cap L_2\), \(L_1 \cap L_3\), \(L_1 \cap L_4\), \(L_1 \cap L_5\), \(L_3 \cap L_4\)

Показать решение

Ключевая идея: сначала уточним каждый язык.

Языки:
- \(L_1 = \{0, 1, 00, 11, 000, 111, ...\}\) — строки из одинаковых символов (все нули или все единицы, длина \(\geq 1\))
  
  Формально: \(L_1 = \{0^n : n \geq 1\} \cup \{1^n : n \geq 1\}\)
- \(L_2 = \{0, 1\}^*\) — все двоичные строки
- \(L_3 = \{w \mid |w| = 1\}\) — \(L_3 = \{0, 1\}\)
- \(L_4 = \{w \mid |w| = 2\}\) — \(L_4 = \{00, 01, 10, 11\}\)
- \(L_5 = \{w \mid |w| \geq 1\}\) — все непустые: \(L_5 = \Sigma^* \setminus \{\epsilon\}\)

(Часть 1a: \(L_1 \cup L_2\))

\(L_1 \subseteq L_2\)
Значит \(L_1 \cup L_2 = L_2 = \{0, 1\}^*\)

(Часть 1b: \(L_3 \cup L_4\))

\(L_3 \cup L_4 = \{0, 1, 00, 01, 10, 11\}\)

(Часть 2a: \(L_1 \cap L_2\))

\(L_1 \subseteq L_2 \Rightarrow L_1 \cap L_2 = L_1 = \{0^n, 1^n : n \geq 1\}\)

(Часть 2b: \(L_1 \cap L_3\))

строки длины 1 в \(L_1\): только \(0\) и \(1\)
\(L_1 \cap L_3 = \{0, 1\}\)

(Часть 2c: \(L_1 \cap L_4\))

строки длины 2 в \(L_1\): только \(00\) и \(11\)
\(L_1 \cap L_4 = \{00, 11\}\)

(Часть 2d: \(L_1 \cap L_5\))

в \(L_1\) нет \(\epsilon\), в \(L_5\) все непустые
\(L_1 \cap L_5 = L_1 = \{0^n, 1^n : n \geq 1\}\)

(Часть 2e: \(L_3 \cap L_4\))

длина не может быть одновременно 1 и 2
\(L_3 \cap L_4 = \emptyset\)

Ответ: 1. \(L_1 \cup L_2 = \{0, 1\}^*\) и \(L_3 \cup L_4 = \{0, 1, 00, 01, 10, 11\}\) 2. - \(L_1 \cap L_2 = \{0^n, 1^n : n \geq 1\}\) - \(L_1 \cap L_3 = \{0, 1\}\) - \(L_1 \cap L_4 = \{00, 11\}\) - \(L_1 \cap L_5 = \{0^n, 1^n : n \geq 1\}\) - \(L_3 \cap L_4 = \emptyset\)

4.37. Разность языков (Лаба 2, Задание 6.2)

Для тех же языков из упражнения 5 найти: 3. \(L_1 \setminus L_2\), \(L_1 \setminus L_3\), \(L_3 \setminus L_4\), \(L_4 \setminus L_5\), \(L_5 \setminus L_4\)

Показать решение

(Часть 3a: \(L_1 \setminus L_2\))

\(L_1 \subseteq L_2 \Rightarrow L_1 \setminus L_2 = \emptyset\)

(Часть 3b: \(L_1 \setminus L_3\))

\(L_1 \setminus L_3 = \{00, 11, 000, 111, 0000, 1111, ...\} = \{0^n, 1^n : n \geq 2\}\)

(Часть 3c: \(L_3 \setminus L_4\))

разные длины \(\Rightarrow L_3 \setminus L_4 = L_3 = \{0, 1\}\)

(Часть 3d: \(L_4 \setminus L_5\))

все строки из \(L_4\) непустые и лежат в \(L_5\)
\(L_4 \setminus L_5 = \emptyset\)

(Часть 3e: \(L_5 \setminus L_4\))

все непустые строки, кроме длины 2
\(L_5 \setminus L_4 = \{w \in \Sigma^* : |w| \geq 1, |w| \neq 2\} = \{w \in \Sigma^* : |w| = 1\} \cup \{w \in \Sigma^* : |w| \geq 3\}\)

Ответ: 3. - \(L_1 \setminus L_2 = \emptyset\) - \(L_1 \setminus L_3 = \{0^n, 1^n : n \geq 2\}\) - \(L_3 \setminus L_4 = \{0, 1\}\) - \(L_4 \setminus L_5 = \emptyset\) - \(L_5 \setminus L_4 = \{w : |w| \neq 2, |w| \geq 1\}\) (все непустые строки, кроме длины 2)

4.38. Дополнения языков (Лаба 2, Задание 6.3)

Для тех же языков из упражнения 5 найти: 4. \(\overline{L_1}\), \(\overline{L_2}\), \(\overline{L_3}\), \(\overline{L_5 \setminus L_4}\)

Показать решение

(Часть 4a: \(\overline{L_1}\))

\(L_1 = \{0^n, 1^n : n \geq 1\}\)
\(\overline{L_1} = \{0, 1\}^* \setminus L_1\)
в частности: \(\overline{L_1} = \{\epsilon\} \cup \{w : w \text{ содержит и } 0\text{, и } 1\}\)

(Часть 4b: \(\overline{L_2}\))

\(L_2 = \{0, 1\}^*\)
\(\overline{L_2} = \emptyset\)

(Часть 4c: \(\overline{L_3}\))

\(L_3 = \{0, 1\}\)
\(\overline{L_3} = \{\epsilon\} \cup \{w : |w| \neq 1\}\)

(Часть 4d: \(\overline{L_5 \setminus L_4}\))

\(L_5 \setminus L_4 = \{w : |w| \neq 2, |w| \geq 1\}\)
дополнение: пустая строка и все строки длины 2
\(\overline{L_5 \setminus L_4} = \{\epsilon\} \cup L_4 = \{\epsilon, 00, 01, 10, 11\}\)

Ответ: 4. - \(\overline{L_1} = \{\epsilon\} \cup \{w : w \text{ содержит и } 0\text{, и } 1\}\) (пустая строка или «смешанные» строки) - \(\overline{L_2} = \emptyset\) - \(\overline{L_3} = \{\epsilon\} \cup \{w : |w| \neq 1\}\) (пустая строка и строки длины не 1) - \(\overline{L_5 \setminus L_4} = \{\epsilon, 00, 01, 10, 11\}\) (пустая строка и все строки длины 2)

4.39. Конкатенация языков (Лаба 2, Задание 6.4)

Для тех же языков из упражнения 5 найти: 5. \(L_1L_2\), \(L_3L_4\), \(L_4L_3\)

Показать решение

(Часть 5a: \(L_1L_2\))

\(L_1 = \{0^n, 1^n : n \geq 1\}\)
\(L_2 = \{0, 1\}^*\) (все двоичные строки)
\(L_1L_2 = \{xy : x \in L_1, y \in L_2\}\)

Разбор: для каждой строки из \(L_1\) (повтор одного символа) дописываем справа любую строку из \(L_2\).
Примеры:
- \(x = 0 \in L_1\), \(y = 010 \in L_2\): \(xy = 0010\)
- \(x = 111 \in L_1\), \(y = 00 \in L_2\): \(xy = 11100\)
Какие строки получаются? Докажем, что \(L_1L_2\) совпадает со всеми непустыми двоичными строками.
- Для \(w = \epsilon\) нужны \(x \in L_1\) и \(y \in L_2\) с \(xy = \epsilon\) — невозможно, так как в \(L_1\) нет \(\epsilon\).
- Если \(w\) начинается с 0, пишем \(w = 0w'\), где \(w'\) — любая строка. Возьмём \(x = 0 \in L_1\) и \(y = w' \in L_2\).
- Если \(w\) начинается с 1, пишем \(w = 1w'\). Возьмём \(x = 1 \in L_1\) и \(y = w' \in L_2\).
Итог: \(L_1L_2 = \Sigma^* \setminus \{\epsilon\} = L_5\)

(Часть 5b: \(L_3L_4\))

\(L_3 = \{0, 1\}\) (строки длины 1)
\(L_4 = \{00, 01, 10, 11\}\) (строки длины 2)
\(L_3L_4 = \{xy : x \in L_3, y \in L_4\}\)

Все склейки:
- \(0 \cdot 00 = 000\)
- \(0 \cdot 01 = 001\)
- \(0 \cdot 10 = 010\)
- \(0 \cdot 11 = 011\)
- \(1 \cdot 00 = 100\)
- \(1 \cdot 01 = 101\)
- \(1 \cdot 10 = 110\)
- \(1 \cdot 11 = 111\)
Результат: \(L_3L_4 = \{000, 001, 010, 011, 100, 101, 110, 111\} = \Sigma^3\) (все 3-битовые строки)

(Часть 5c: \(L_4L_3\))

\(L_4 = \{00, 01, 10, 11\}\), \(L_3 = \{0, 1\}\)
\(L_4L_3 = \{xy : x \in L_4, y \in L_3\}\)

Все склейки:
- \(00 \cdot 0 = 000\)
- \(00 \cdot 1 = 001\)
- \(01 \cdot 0 = 010\)
- \(01 \cdot 1 = 011\)
- \(10 \cdot 0 = 100\)
- \(10 \cdot 1 = 101\)
- \(11 \cdot 0 = 110\)
- \(11 \cdot 1 = 111\)
Результат: \(L_4L_3 = \{000, 001, 010, 011, 100, 101, 110, 111\} = \Sigma^3\) (все 3-битовые строки)

Ответ: 5. - \(L_1L_2 = \Sigma^+ = \{w : |w| \geq 1\}\) (все непустые строки) - \(L_3L_4 = \Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}\) - \(L_4L_3 = \Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}\)

4.40. Звезда Клини и плюс (Лаба 2, Задание 6.5)

Для тех же языков из упражнения 5 найти: 6. \(L_2^*\), \(L_3^*\), \(L_4^*\)

Показать решение

(Часть 6a: \(L_2^*\))

\(L_2 = \{0, 1\}^*\) (все двоичные строки)
\(L_2^*\) — все конкатенации нуля или более строк из \(L_2\)

Разбор: любая склейка строк из \(L_2\) снова даёт двоичную строку.
Включения в обе стороны:
- Любая строка из \(L_2^*\) двоична? Да, так как сомножители из \(L_2\) двоичны.
- Любая двоичная строка лежит в \(L_2^*\)? Да: \(w = w\) как одна конкатенация из \(L_2\).
Итог: \(L_2^* = L_2 = \{0, 1\}^*\)

(Часть 6b: \(L_3^*\))

\(L_3 = \{0, 1\}\) (односимвольные строки)
\(L_3^*\) — конкатенации нуля или более строк из \(L_3\)

Смысл: склеивая любое число символов 0 и 1, получаем любую двоичную строку.
Проверка:
- любая такая склейка — двоичная строка;
- любую двоичную можно разбить на одиночные 0 и 1;
- ноль сомножителей даёт \(\epsilon\).
Итог: \(L_3^* = \{0, 1\}^*\)

(Часть 6c: \(L_4^*\))

\(L_4 = \{00, 01, 10, 11\}\) (все строки длины 2)
\(L_4^*\) — конкатенации нуля или более строк из \(L_4\)

Разбор: каждая строка в \(L_4^*\) получается склейкой блоков длины 2.
- ноль склеек: \(\epsilon\)
- одна склейка: любая строка из \(L_4\)
- две склейки: любая строка длины 4 из двух блоков по 2 символа
- три склейки: длина 6
- вообще: длины \(2n\)
Наблюдение: \(n\) строк длины 2 дают строку длины \(2n\).
Возможные длины: \(2 \cdot 0 = 0\) (пустая), \(2 \cdot 1 = 2\), \(2 \cdot 2 = 4\), … — все чётные длины.
Итог: \(L_4^* = \{w : |w| \text{ чётна}\}\) (все двоичные строки чётной длины, включая \(\epsilon\))

Ответ: 6. - \(L_2^* = \{0, 1\}^*\) (все двоичные строки) - \(L_3^* = \{0, 1\}^*\) (все двоичные строки) - \(L_4^* = \{w \in \{0, 1\}^* : |w| \text{ чётна}\}\) (двоичные строки чётной длины, включая \(\epsilon\))

4.41. Минимальный алфавит по языку (Туториал 2, Пример 1)

Для языка \(L = \{x : x \in \Sigma^*, x \text{ начинается с } 0\}\) определите минимальный алфавит \(\Sigma\).

Показать решение

Ключевая идея: минимальный алфавит содержит все используемые символы и не содержит лишних.

Язык: все строки, начинающиеся с цифры 0: \(0, 00, 01, 000, 001, ...\)
Символы: нужен 0; после ведущего 0 могут идти любые символы алфавита.
Минимум: чтобы были не только «0», нужен ещё хотя бы один символ; минимально — добавить 1.
Проверка: при \(\Sigma = \{0, 1\}\) язык \(L = \{0x : x \in \Sigma^*\}\) согласуется с описанием.

Ответ: минимальный алфавит \(\Sigma = \{0, 1\}\) (или любой двухсимвольный, где один символ — 0).

4.42. Ассоциативность и нейтральный элемент (Туториал 2, Пример 2)

Проверьте ассоциативность конкатенации и укажите нейтральный элемент.

Показать решение

Ключевая идея: показать \((xy)z = x(yz)\) и найти \(e\) с \(ex = xe = x\).

Ассоциативность:

Пусть \(x = x_1x_2...x_m\), \(y = y_1y_2...y_n\), \(z = z_1z_2...z_p\)
\((xy)z\): \(xy = x_1...x_my_1...y_n\), затем \((xy)z = x_1...x_my_1...y_nz_1...z_p\)
\(x(yz)\): \(yz = y_1...y_nz_1...z_p\), затем \(x(yz) = x_1...x_my_1...y_nz_1...z_p\)
Вывод: \((xy)z = x(yz)\).

Нейтральный элемент:

\(\epsilon\): \(\epsilon \cdot x = x\), \(x \cdot \epsilon = x\)
Вывод: нейтральный элемент — \(\epsilon\).

Ответ: конкатенация ассоциативна: \((xy)z = x(yz)\). Нейтральный элемент — \(\epsilon\): \(\epsilon x = x\epsilon = x\) для всех строк \(x\).